/**
 * 合并两个有序链表
 * 1,2,3    1,3,4   ->  1,1,2,3,3,4
 */
public class LeetCode21 {
    public static void main(String[] args) {
        ListNode21 list1 = new ListNode21(1, new ListNode21(2, new ListNode21(3, null)));
        ListNode21 list2 = new ListNode21(1, new ListNode21(3, new ListNode21(4, null)));

        ListNode21 listNode = mergeTwoLists(list1, list2);
//        ListNode21 listNode =  mergeTwoLists2(list1,list2);
//        ListNode21 listNode =  mergeTwoListss(list1,list2);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }


    /**
     * mergeTwoLists( l1=[1,3,8,9] , l2 = [2,4]){
     * mergeTwoLists( l1=[3,8,9] , l2= [2,4]){
     * mergeTwoLists( l1=[3,8,9] , l2= [4]){
     * mergeTwoLists( l1=[8,9] , l2= [4]){
     * mergeTwoLists( l1=[8,9] , l2= []){
     * mergeTwoLists( l1=[8,9] , l2= [2,4]){
     * return [8,9];
     * }
     * return 4;
     * }
     * return 3;
     * }
     * return 2;
     * }
     * return 1;
     * }
     */
    public static ListNode21 mergeTwoListss(ListNode21 l1, ListNode21 l2) {
        if (l2 == null) {
            return l1;
        }
        if (l1 == null) {
            return l2;
        }
        if (l1.val < l2.val) {
            l1.next = mergeTwoListss(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoListss(l1, l2.next);
            return l2;
        }
    }

    /**
     * 递归
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode21 mergeTwoLists(ListNode21 l1, ListNode21 l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }


    /**
     * 双指针
     */
    public static ListNode21 mergeTwoLists2(ListNode21 l1, ListNode21 l2) {
        ListNode21 s = new ListNode21(-1, null);
        ListNode21 p = s;  //新链表的头
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        if (l1 != null) {
            p.next = l1;
        }
        if (l2 != null) {
            p.next = l2;
        }

        return s.next;
    }


}

class ListNode21 {
    int val;
    ListNode21 next;

    ListNode21() {
    }

    ListNode21(int val) {
        this.val = val;
    }

    ListNode21(int val, ListNode21 next) {
        this.val = val;
        this.next = next;
    }
}

